package com.yanceysong.codetop.s21_s30;

import com.yanceysong.common.ListNode;

/**
 * @ClassName S29_Easy_160_相交链表
 * @Description
 * @date 2025/09/16
 * @Author yanceysong
 * @Version 1.0
 */
public class S29_Easy_160_相交链表 {

    /**
     * S29_Easy_160_相交链表
     * <p>
     * LeetCode：
     * <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/">...</a>
     * <p>
     * 题目描述：
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
     * 如果两个链表不存在相交节点，返回 null 。
     * <p>
     * 图形描述题目中链表的相交情况：
     * <p>
     * 示例 1：
     * <p>
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Intersected at '8'
     * 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
     * <p>
     * 示例 2：
     * <p>
     * 输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
     * 输出：Intersected at '2'
     * <p>
     * 示例 3：
     * <p>
     * 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
     * 输出：null
     * 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
     * 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
     * <p>
     * 提示：
     * <p>
     * listA 中节点数目为 m
     * listB 中节点数目为 n
     * 1 <= m, n <= 3 * 10^4
     * 1 <= Node.val <= 10^5
     * 0 <= skipA < m
     * 0 <= skipB < n
     * 如果 listA 和 listB 没有交点，intersectVal 为 0
     * 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
     * <p>
     * 使用双指针法寻找两个链表的相交节点
     * <p>
     * 算法原理：
     * 1. 两个指针分别从两个链表的头部开始遍历
     * 2. 当其中一个指针遍历完自己的链表后，转到另一个链表的头部继续遍历
     * 3. 另一个指针做同样的操作
     * 4. 如果两链表相交，两指针最终会在相交点相遇
     * 5. 如果两链表不相交，两指针最终都会变为null
     * <p>
     * 核心思想：
     * - 通过指针切换，消除两链表长度差异的影响
     * - 每个指针都会走 (lenA + lenB) 的距离
     * - 相交情况：两指针会在相交点相遇
     * - 不相交情况：两指针都会在遍历完两个链表后同时为null
     * <p>
     * 数学原理：
     * 设链表A的长度为a，链表B的长度为b，相交部分长度为c
     * - 链表A独有部分长度：a - c
     * - 链表B独有部分长度：b - c
     * - 指针pointerA走过的路径：(a - c) + c + (b - c) = a + b - c
     * - 指针pointerB走过的路径：(b - c) + c + (a - c) = a + b - c
     * - 两指针走过相同距离后在相交点相遇
     * <p>
     * 图解示例：有相交的情况
     * <p>
     * 链表结构：
     * listA: 4  →  1  →  8  →  4  →  5
     * ↑
     * listB: 5  →  6  →  1 ↗
     * <p>
     * 相交点为节点8，skipA=2, skipB=3
     * <p>
     * 双指针遍历过程：
     * <p>
     * 初始状态：
     * pointerA  →  4 (listA头部)
     * pointerB  →  5 (listB头部)
     * <p>
     * 第1步：
     * pointerA: 4  →  1
     * pointerB: 5  →  6
     * <p>
     * 第2步：
     * pointerA: 1  →  8 (相交点)
     * pointerB: 6  →  1
     * <p>
     * 第3步：
     * pointerA: 8  →  4
     * pointerB: 1  →  8 (相交点)
     * <p>
     * 第4步：
     * pointerA: 4  →  5
     * pointerB: 8  →  4
     * <p>
     * 第5步：
     * pointerA: 5  →  null (listA结束，切换到listB头部)
     * pointerB: 4  →  5
     * <p>
     * 第6步：
     * pointerA: null  →  5 (开始遍历listB)
     * pointerB: 5  →  null (listB结束，切换到listA头部)
     * <p>
     * 第7步：
     * pointerA: 5  →  6
     * pointerB: null  →  4 (开始遍历listA)
     * <p>
     * 第8步：
     * pointerA: 6  →  1
     * pointerB: 4  →  1
     * <p>
     * 第9步：
     * pointerA: 1  →  8 (相交点)
     * pointerB: 1  →  8 (相交点)
     * <p>
     * 此时 pointerA == pointerB == 节点8，找到相交点！
     * <p>
     * 图解示例：无相交的情况
     * <p>
     * 链表结构：
     * listA: 2  →  6  →  4
     * listB: 1  →  5
     * <p>
     * 双指针遍历过程：
     * <p>
     * pointerA遍历路径：2 → 6 → 4 →  null → 1 → 5 → null
     * pointerB遍历路径：1 → 5 → null → 2 → 6 → 4 → null
     * <p>
     * 最终两指针都为null，返回null表示无相交
     * <p>
     * 可视化路径对比：
     * <p>
     * 有相交情况 (listA=[4,1,8,4,5], listB=[5,6,1,8,4,5])：
     * pointerA: 4  →  1  →  8  →  4 →  5  →  5  →  6  →  1  →  8 (在第二次到达8时相遇)
     * pointerB: 5  →  6  →  1 →  8  →  4  →  5  →  4  →  1  →  8 (在第二次到达8时相遇)
     * <p>
     * 无相交情况 (listA=[2,6,4], listB=[1,5])：
     * pointerA: 2 → 6 → 4 → 1 → 5 → null
     * pointerB: 1 → 5 → 2 → 6 → 4 → null
     * <p>
     * 时间复杂度：O(m + n)，其中m和n分别是两个链表的长度
     * 空间复杂度：O(1)，只使用了两个指针变量
     * <p>
     * 算法优势：
     * 1. 不需要计算链表长度
     * 2. 一次遍历即可完成
     * 3. 空间复杂度为O(1)
     * 4. 代码简洁优雅
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 边界条件检查：如果任一链表为空，则不可能有相交点
        if (headA == null || headB == null) {
            return null;
        }

        // 双指针分别指向两个链表的头节点
        ListNode pointerA = headA;  // 指针A，初始指向链表A的头部
        ListNode pointerB = headB;  // 指针B，初始指向链表B的头部

        // 当两指针不相等时继续遍历
        // 相等的情况包括：1) 找到相交点 2) 都为null（无相交）
        while (pointerA != pointerB) {
            // 指针A的移动策略：
            // 如果还在链表A中，移动到下一个节点
            // 如果已到链表A末尾(null)，切换到链表B的头部开始遍历
            pointerA = (pointerA != null) ? pointerA.next : headB;

            // 指针B的移动策略：
            // 如果还在链表B中，移动到下一个节点
            // 如果已到链表B末尾(null)，切换到链表A的头部开始遍历
            pointerB = (pointerB != null) ? pointerB.next : headA;
        }

        // 循环结束时，pointerA == pointerB
        // 情况1：找到相交点，返回该节点
        // 情况2：无相交点，两指针都为null，返回null
        return pointerA;
    }

    public static void main(String[] args) {
        S29_Easy_160_相交链表 solution = new S29_Easy_160_相交链表();

        System.out.println("=== 相交链表算法测试开始 ===");

        // 测试1: 题目示例1 - 有相交点的情况
        System.out.println("\n--- 测试1: 基础相交情况 intersectVal=8 ---");
        testIntersectionCase1(solution);

        // 测试2: 题目示例2 - 有相交点的情况（不同长度）
        System.out.println("\n--- 测试2: 不同长度相交 intersectVal=2 ---");
        testIntersectionCase2(solution);

        // 测试3: 题目示例3 - 无相交点的情况
        System.out.println("\n--- 测试3: 无相交情况 ---");
        testNoIntersectionCase(solution);

        // 测试4: 边界情况测试
        System.out.println("\n--- 测试4: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试5: 相同长度链表测试
        System.out.println("\n--- 测试5: 相同长度链表 ---");
        testSameLengthLists(solution);

        // 测试6: 单节点相交测试
        System.out.println("\n--- 测试6: 单节点相交 ---");
        testSingleNodeIntersection(solution);

        // 测试7: 完全重合的链表
        System.out.println("\n--- 测试7: 完全重合链表 ---");
        testCompleteOverlapLists(solution);

        // 测试8: 长度差异很大的链表
        System.out.println("\n--- 测试8: 长度差异大的链表 ---");
        testVeryDifferentLengths(solution);

        // 测试9: 相交点在末尾
        System.out.println("\n--- 测试9: 相交点在末尾 ---");
        testIntersectionAtEnd(solution);

        // 测试10: 相交点在开头
        System.out.println("\n--- 测试10: 相交点在开头 ---");
        testIntersectionAtBeginning(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基础相交情况：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
     * 链表结构：
     * listA: 4  →  1  →  8  →  4  →  5
     * ↑
     * listB: 5  →  6  →  1 ↗
     */
    private static void testIntersectionCase1(S29_Easy_160_相交链表 solution) {
        // 构建相交的链表
        ListNode intersectNode = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        intersectNode.next = node4;
        node4.next = node5;

        // 构建链表A: 4  →  1  →  8  →  4  →  5
        ListNode headA = new ListNode(4);
        ListNode nodeA1 = new ListNode(1);
        headA.next = nodeA1;
        nodeA1.next = intersectNode;

        // 构建链表B: 5  →  6  →  1  →  8  →  4  →  5
        ListNode headB = new ListNode(5);
        ListNode nodeB6 = new ListNode(6);
        ListNode nodeB1 = new ListNode(1);
        headB.next = nodeB6;
        nodeB6.next = nodeB1;
        nodeB1.next = intersectNode;

        System.out.println("构建链表:");
        System.out.println("listA: 4  →  1  →  8  →  4  →  5");
        System.out.println("listB: 5  →  6  →  1  →  8  →  4  →  5");
        System.out.println("相交点: 8");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 8)");
        assert result != null && result.val == 8 : "应该找到值为8的相交点";
        assert result == intersectNode : "应该返回相同的节点引用";
        System.out.println("✓ 基础相交测试通过");
    }

    /**
     * 测试不同长度相交：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4]
     */
    private static void testIntersectionCase2(S29_Easy_160_相交链表 solution) {
        // 构建相交部分：2  →  4
        ListNode intersectNode = new ListNode(2);
        ListNode node4 = new ListNode(4);
        intersectNode.next = node4;

        // 构建链表A: 1  →  9  →  1  →  2  →  4
        ListNode headA = new ListNode(1);
        ListNode nodeA9 = new ListNode(9);
        ListNode nodeA1 = new ListNode(1);
        headA.next = nodeA9;
        nodeA9.next = nodeA1;
        nodeA1.next = intersectNode;

        // 构建链表B: 3  →  2  →  4
        ListNode headB = new ListNode(3);
        headB.next = intersectNode;

        System.out.println("构建链表:");
        System.out.println("listA: 1  →  9  →  1  →  2  →  4");
        System.out.println("listB: 3  →  2  →  4");
        System.out.println("相交点: 2");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 2)");
        assert result != null && result.val == 2 : "应该找到值为2的相交点";
        assert result == intersectNode : "应该返回相同的节点引用";
        System.out.println("✓ 不同长度相交测试通过");
    }

    /**
     * 测试无相交情况：listA = [2,6,4], listB = [1,5]
     */
    private static void testNoIntersectionCase(S29_Easy_160_相交链表 solution) {
        // 构建不相交的链表A: 2  →  6  →  4
        ListNode headA = new ListNode(2);
        ListNode nodeA6 = new ListNode(6);
        ListNode nodeA4 = new ListNode(4);
        headA.next = nodeA6;
        nodeA6.next = nodeA4;

        // 构建不相交的链表B: 1  →  5
        ListNode headB = new ListNode(1);
        ListNode nodeB5 = new ListNode(5);
        headB.next = nodeB5;

        System.out.println("构建链表:");
        System.out.println("listA: 2  →  6  →  4");
        System.out.println("listB: 1  →  5");
        System.out.println("无相交点");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: null)");
        assert result == null : "应该返回null表示无相交";
        System.out.println("✓ 无相交测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S29_Easy_160_相交链表 solution) {
        // 测试空链表
        ListNode result1 = solution.getIntersectionNode(null, null);
        System.out.println("空链表测试: getIntersectionNode(null, null) -> " + (result1 != null ? result1.val : "null") + " (期望: null)");
        assert result1 == null : "两个空链表应该返回null";

        // 测试一个空链表
        ListNode singleNode = new ListNode(1);
        ListNode result2 = solution.getIntersectionNode(singleNode, null);
        System.out.println("单边空链表测试: getIntersectionNode([1], null) -> " + (result2 != null ? result2.val : "null") + " (期望: null)");
        assert result2 == null : "一个空链表应该返回null";

        ListNode result3 = solution.getIntersectionNode(null, singleNode);
        System.out.println("单边空链表测试: getIntersectionNode(null, [1]) -> " + (result3 != null ? result3.val : "null") + " (期望: null)");
        assert result3 == null : "一个空链表应该返回null";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试相同长度链表
     */
    private static void testSameLengthLists(S29_Easy_160_相交链表 solution) {
        // 构建相交点
        ListNode intersectNode = new ListNode(99);

        // 构建相同长度的链表A: 1  →  2  →  99
        ListNode headA = new ListNode(1);
        ListNode nodeA2 = new ListNode(2);
        headA.next = nodeA2;
        nodeA2.next = intersectNode;

        // 构建相同长度的链表B: 3  →  4  →  99
        ListNode headB = new ListNode(3);
        ListNode nodeB4 = new ListNode(4);
        headB.next = nodeB4;
        nodeB4.next = intersectNode;

        System.out.println("构建相同长度链表:");
        System.out.println("listA: 1  →  2  →  99");
        System.out.println("listB: 3  →  4  →  99");
        System.out.println("相交点: 99");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 99)");
        assert result != null && result.val == 99 : "应该找到值为99的相交点";
        System.out.println("✓ 相同长度链表测试通过");
    }

    /**
     * 测试单节点相交
     */
    private static void testSingleNodeIntersection(S29_Easy_160_相交链表 solution) {
        // 相交点就是单个节点
        ListNode intersectNode = new ListNode(42);

        System.out.println("构建单节点相交:");
        System.out.println("listA: 42");
        System.out.println("listB: 42 (同一个节点)");

        ListNode result = solution.getIntersectionNode(intersectNode, intersectNode);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 42)");
        assert result != null && result.val == 42 : "应该找到值为42的相交点";
        assert result == intersectNode : "应该返回相同的节点引用";
        System.out.println("✓ 单节点相交测试通过");
    }

    /**
     * 测试完全重合的链表
     */
    private static void testCompleteOverlapLists(S29_Easy_160_相交链表 solution) {
        // 构建完全相同的链表：1  →  2  →  3
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        head.next = node2;
        node2.next = node3;

        System.out.println("构建完全重合链表:");
        System.out.println("listA: 1  →  2  →  3");
        System.out.println("listB: 1  →  2  →  3 (完全相同)");
        System.out.println("相交点: 1 (从头开始相交)");

        ListNode result = solution.getIntersectionNode(head, head);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 1)");
        assert result != null && result.val == 1 : "应该找到值为1的相交点";
        assert result == head : "应该返回头节点";
        System.out.println("✓ 完全重合链表测试通过");
    }

    /**
     * 测试长度差异很大的链表
     */
    private static void testVeryDifferentLengths(S29_Easy_160_相交链表 solution) {
        // 构建相交点
        ListNode intersectNode = new ListNode(100);

        // 构建长链表A: 1  →  2  →  3  →  4  →  5  →  100
        ListNode headA = new ListNode(1);
        ListNode current = headA;
        for (int i = 2; i <= 5; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }
        current.next = intersectNode;

        // 构建短链表B: 99  →  100
        ListNode headB = new ListNode(99);
        headB.next = intersectNode;

        System.out.println("构建长度差异大的链表:");
        System.out.println("listA: 1  →  2  →  3  →  4  →  5  →  100 (长度6)");
        System.out.println("listB: 99  →  100 (长度2)");
        System.out.println("相交点: 100");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 100)");
        assert result != null && result.val == 100 : "应该找到值为100的相交点";
        assert result == intersectNode : "应该返回相同的节点引用";
        System.out.println("✓ 长度差异大的链表测试通过");
    }

    /**
     * 测试相交点在末尾
     */
    private static void testIntersectionAtEnd(S29_Easy_160_相交链表 solution) {
        // 相交点（末尾节点）
        ListNode intersectNode = new ListNode(999);

        // 构建链表A: 10  →  20  →  999
        ListNode headA = new ListNode(10);
        ListNode nodeA20 = new ListNode(20);
        headA.next = nodeA20;
        nodeA20.next = intersectNode;

        // 构建链表B: 30  →  999
        ListNode headB = new ListNode(30);
        headB.next = intersectNode;

        System.out.println("构建相交点在末尾的链表:");
        System.out.println("listA: 10  →  20  →  999");
        System.out.println("listB: 30  →  999");
        System.out.println("相交点: 999 (末尾节点)");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 999)");
        assert result != null && result.val == 999 : "应该找到值为999的相交点";
        assert result == intersectNode : "应该返回相同的节点引用";
        System.out.println("✓ 相交点在末尾测试通过");
    }

    /**
     * 测试相交点在开头（一个链表是另一个链表的子集）
     */
    private static void testIntersectionAtBeginning(S29_Easy_160_相交链表 solution) {
        // 构建链表：1  →  2  →  3
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        head.next = node2;
        node2.next = node3;

        // 链表A就是完整链表：1  →  2  →  3
        ListNode headA = head;

        // 链表B是从中间开始的子链表：2  →  3
        ListNode headB = node2;

        System.out.println("构建相交点在开头的链表:");
        System.out.println("listA: 1  →  2  →  3");
        System.out.println("listB: 2  →  3 (从A的中间开始)");
        System.out.println("相交点: 2 (B的开头节点)");

        ListNode result = solution.getIntersectionNode(headA, headB);
        System.out.println("getIntersectionNode() -> " + (result != null ? result.val : "null") + " (期望: 2)");
        assert result != null && result.val == 2 : "应该找到值为2的相交点";
        assert result == node2 : "应该返回相同的节点引用";
        System.out.println("✓ 相交点在开头测试通过");
    }
}
